﻿#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//用顺序表实现堆
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;

//默认初始化堆
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 删除堆顶的数据
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);

void swap(HPDataType* a, int n, int i)
{
	HPDataType tmp = a[n];
	a[n] = a[i];
	a[i] = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* a, int child)
{
	while (child)
	{
		if (a[(child - 1) / 2] > a[child])
		{
			swap(a, (child - 1) / 2, child);
			child = (child - 1) / 2;
		}
		else
			break;
	}
}

//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 假设法，选出左右孩⼦中⼩的那个孩⼦
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			swap(a, child, parent);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	free(hp);
}

void HPcapacheck(Heap* hp)//堆的容量检查，扩容
{
	if (hp->capacity == 0)
	{
		hp->a = (HPDataType*)malloc(4 * sizeof(HPDataType));
		hp->capacity = 4;
	}
	else if (hp->capacity == hp->size)
	{
		HPDataType* p = (HPDataType*)realloc(hp->a, 2 * hp->capacity * sizeof(HPDataType));
		if (p == NULL)
		{
			perror("realloc");
		}
		hp->a = p;
		p = NULL;
		hp->capacity = hp->capacity * 2;
	}
}

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	HPcapacheck(hp);
	hp->a[hp->size++] = x;
	AdjustUp(hp->a, hp->size - 1);
}

void HeapPop(Heap* hp)
{
	assert(hp && hp->size);
	swap(hp->a, hp->size - 1, 0);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);
}

HPDataType HeapTop(Heap* hp)
{
	assert(hp && hp->size);
	return hp->a[0];
}

int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

int main()
{
	Heap* hp = (Heap*)malloc(sizeof(Heap));
	HeapInit(hp);
	HeapPush(hp, 5);
	HeapPush(hp, 3);
	HeapPush(hp, 6);
	HeapPush(hp, 2);
	HeapPush(hp, 7);
	HeapPop(hp);
	HeapPop(hp);
	HeapPop(hp);
	HeapPop(hp);
	HeapPop(hp);
	HeapDestory(hp);
	hp = NULL;
	return 0;
}